/**
 * 在二叉搜索树中，非空左子树的所有键值小于其根节点的键值
 * 非空右子树的所有键值大于其根节点的键值
 * 左右子树本身也都是二叉搜索树
 */

function SearchTree() {
    function Node(key) {
        this.key = key
        this.left = null
        this.right = null
    }
    // 保存根节点
    this.root = null
    this.i = 1
    // 向树中插入数据
    SearchTree.prototype.insert = function (key) {
        var newNode = new Node(key)
        // 没有根节点情况
        if (this.root === null) {
            this.root = newNode
        } else {
            this.insertNode(this.root, newNode)
        }
    }
    // 树中插入数据
    SearchTree.prototype.insertNode = function (node, newNode) {
        // 向左边树插入数据
        if (newNode.key < node.key) {
            if (node.left === null) {
                node.left = newNode
            } else {
                // 左边的节点上已经有了内容
                this.insertNode(node.left, newNode)
            }
        } else {
            // 向右边的节点插入数据
            if (node.right === null) {
                node.right = newNode
            } else {
                // 右边的节点上已经有了节点
                this.insertNode(node.right, newNode)
            }
        }
    }
    // 先序遍历
    SearchTree.prototype.preOrderTraversal = function (handle) {
        this.preOrderTranversalNode(this.root, handle)
    }
    SearchTree.prototype.preOrderTranversalNode = function (node, handle) {
        if (node !== null) {
            // 打印一下节点的值
            // console.log(node.key);
            // 先遍历左边的树
            console.log(node.key);
            this.preOrderTranversalNode(node.left, handle)
            // 遍历右边的树
            this.preOrderTranversalNode(node.right, handle)
        }
    }
    // 中序遍历
    SearchTree.prototype.inOrderTraversal = function (handle) {
        this.inOrderTraversalNode(this.root, handle)
    }
    SearchTree.prototype.inOrderTraversalNode = function (node, handle) {
        if (node !== null) {
            this.inOrderTraversalNode(node.left, handle)
            console.log(node.key);
            this.inOrderTraversalNode(node.right, handle)
        }
    }
    // 后序遍历
    SearchTree.prototype.postOrderTraversal = function (handle) {
        this.postOrderTraversalNode(this.root, handle)
    }
    SearchTree.prototype.postOrderTraversalNode = function (node, handle) {
        if (node !== null) {
            this.postOrderTraversalNode(node.left, handle)
            this.postOrderTraversalNode(node.right, handle)
            console.log(node.key);
        }
    }
    // 最大最小值
    SearchTree.prototype.min = function () {
        var node = this.root
        while (node.left !== null) {
            node = node.left
        }
        return node.key
    }
    SearchTree.prototype.max = function () {
        var node = this.root
        while (node.right !== null) {
            node = node.right
        }
        return node.key
    }
    // 搜索特定的值
    SearchTree.prototype.search = function (key) {
        return this.searchNode(this.root, key)
    }
    SearchTree.prototype.searchNode = function (node, key) {
        if (node === null) {
            return false
        }
        if (node.key > key) {
            return this.searchNode(node.left, key)
        } else if (node.key < key) {
            return this.searchNode(node.right, key)
        } else {
            return true
        }
    }
    // 删除节点
    SearchTree.prototype.remove = function (node) {
        var current = this.root
        var parent = this.root
        var isLeftChild = true
        // 查找要删除的节点
        while (node.key !== key) {
            parent = current
            if (key < current.key) {
                isLeftChild = true
                current = current.left
            } else {
                isLeftChild = false
                current = current.right
            }
            // 说明没有找到节点
            if (current === null) {
                return false
            }
            // 删除的是叶节点
            if (current.left === null & current.right === null) {
                if (current == this.root) {
                    this.root = null
                } else if (isLeftChild) {
                    parent.left = null
                } else {
                    parent.right = null
                }
            }
            // 删除的是只有一个子节点的节点
            else if (current.left === null || current.right === null) {
                if (isLeftChild) {
                    parent.left = current.left
                } else {
                    parent.right = current.right
                }
            }
        }
    }
}

// 测试代码
var bst = new SearchTree()

// 插入数据
bst.insert(11)
bst.insert(7)
bst.insert(15)
bst.insert(5)
bst.insert(3)
bst.insert(9)
bst.insert(8)
bst.insert(10)
bst.insert(13)
bst.insert(12)
bst.insert(14)
bst.insert(20)
bst.insert(18)
bst.insert(25)
bst.insert(6)
var resultString = ""
// bst.preOrderTraversal(function (key) {
//     resultString += key + " "
// })

bst.postOrderTraversal(function (key) {
    resultString += key + " "
})
console.log('最小值:', bst.min());
console.log('最大值:', bst.max());
console.log(bst.search(11));
console.log(bst.search(111));
// bst.inOrderTraversal(function (key) {
//     resultString += key + " "
// })

// bst.postOrderTraversal(function (key) {
//     resultString += key + ''
// })